package medium;
/*
215. 数组中的第K个最大元素
解题思路：快速排序
 */
public class LeeCode215 {

  public static void main(String[] args) {
    int[] num = {3, 2, 1, 5, 6, 4};
    System.out.println(new LeeCode215().findKthLargest(num, 2));
  }

  public int findKthLargest(int[] nums, int k) {
    quick(nums,0,nums.length - 1);
    return nums[k - 1];
  }

  public void quick(int[]arr,int left,int right){
    int l = left;
    int r = right;
    int pivot = arr[(left + right)/2];
    int temp = 0;
    while (l <= r){
      while (arr[l] > pivot){
        l++;
      }
      while (arr[r] < pivot){
        r--;
      }
      if (l >= r){
        break;
      }
      temp = arr[l];
      arr[l] = arr[r];
      arr[r] = temp;
      if (arr[l] == pivot){
        l++;
      }
      if (arr[r] == pivot){
        r--;
      }
    }
    if (l == r){
      l++;
      r--;
    }
    if (l < right){
      quick(arr,l,right);
    }
    if (r > left){
      quick(arr,left,r);
    }
  }
}
